|
In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine. There are several different types of polynomial-time reduction, depending on the details of how the subroutine is used. Intuitively, a polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems for those classes. ==Types of reduction== The three most common types of polynomial-time reduction, from the most to the least restrictive, are polynomial-time many-one reductions, truth-table reductions, and Turing reductions. *A polynomial-time many-one reduction from a problem ''A'' to a problem ''B'' (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem ''A'' into inputs to problem ''B'', such that the transformed problem has the same output as the original problem. An instance ''x'' of problem ''A'' can be solved by applying this transformation to produce an instance ''y'' of problem ''B'', giving ''y'' as the input to an algorithm for problem ''B'', and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type may be denoted by the expression .〔.〕 *A polynomial-time truth-table reduction from a problem ''A'' to a problem ''B'' (both decision problems) is a polynomial time algorithm for transforming inputs to problem ''A'' into a fixed number of inputs to problem ''B'', such that the output for the original problem can be expressed as a function of the outputs for ''B''. The function that maps outputs for ''B'' into the output for ''A'' must be the same for all inputs, so that it can be expressed by a truth table. A reduction of this type may be denoted by the expression .〔.〕 *A polynomial-time Turing reduction from a problem ''A'' to a problem ''B'' is an algorithm that solves problem ''A'' using a polynomial number of calls to a subroutine for problem ''B'', and polynomial time outside of those subroutine calls. Polynomial-time Turing reductions are also known as Cook reductions, named after Stephen Cook. A reduction of this type may be denoted by the expression .〔 The most frequently used of these are the many-one reductions, and in some cases the phrase "polynomial-time reduction" may be used to mean a polynomial-time many-one reduction.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polynomial-time reduction」の詳細全文を読む スポンサード リンク
|